Des graphes identiques... ou pas ? - Corrigé

Énoncé

Voici deux graphes A et B.

1. Donner l'ordre de chacun de ces graphes et leur nombre d'arêtes.

2. Donner leurs matrices d'adjacences.

3. Ces graphes sont-ils identiques ?

Solution 

1. Ces graphes sont tous les deux d'ordre 6 et ont tous les deux 11 arêtes.

2. Matrice d'adjacence du graphe A :  \(A=\begin{pmatrix}0&1&1&1&0&1\\1&0&1&1&0&1\\1&1&0&1&1&0\\1&1&1&0&1&0\\0&0&1&1&0&1\\1&1&0&0&1&0\end{pmatrix}\)

  Matrice d'adjacence du graphe B :  \(B=\begin{pmatrix}0&1&1&1&1&0\\1&0&1&1&0&1\\1&1&0&1&0&1\\1&1&1&0&1&0\\1&0&0&1&0&1\\0&1&1&0&1&0\end{pmatrix}\)  

3. Ces graphes n'ont pas la même matrice d'adjacence. Ils ne sont pas identiques.